Min-cut clustering, based on minimizing one of two heuristic cost-functionsproposed by Shi and Malik, has spawned tremendous research, both analytic andalgorithmic, in the graph partitioning and image segmentation communities overthe last decade. It is however unclear if these heuristics can be derived froma more general principle facilitating generalization to new problem settings.Motivated by an existing graph partitioning framework, we derive relationshipsbetween optimizing relevance information, as defined in the InformationBottleneck method, and the regularized cut in a K-partitioned graph. For fastmixing graphs, we show that the cost functions introduced by Shi and Malik canbe well approximated as the rate of loss of predictive information about thelocation of random walkers on the graph. For graphs generated from a stochasticalgorithm designed to model community structure, the optimal informationtheoretic partition and the optimal min-cut partition are shown to be the samewith high probability.
展开▼
